package com.chj.lintcode.backpack;

public class Code01_Backpack {
	/**
	 * @param m: An integer m denotes the size of a backpack
	 * @param A: Given n items with size A[i]
	 * @return: The maximum size
	 */
	public static int backPack(int m, int[] A) {
		// write your code here
		int n = A.length;
		boolean[][] dp = new boolean[n + 1][m + 1];
		dp[0][0] = true;
		for (int i = 1; i <= m; i++) {
			dp[0][i] = false;
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= A[i - 1]) {
					dp[i][j] |= dp[i - 1][j - A[i - 1]];
				}
			}
		}

		int res = 0;
		for (int i = m; i >= 0; i--) {
			if (dp[n][i]) {
				res = i;
				break;
			}
		}

		return res;
	}

	public static void main(String[] args) {
		{
			int m = 10;
			int[] A = { 3, 4, 8, 5 };
			System.out.println(backPack(m, A));
		}
	}
}
